'''
https://leetcode.cn/problems/smallest-sufficient-team/description/
'''
from collections import defaultdict
from functools import lru_cache
from typing import List

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        m, n = len(req_skills), len(people)
        skills = { req_skills[i]: i for i in range(m)}
        people_skills = [0] *  n
        for i, person_skills in enumerate(people):
            status = 0
            for skill in person_skills:
                status |= 1 << skills[skill]
            people_skills[i] = status
        final_status = (1 << m) - 1
        dp = [defaultdict(int) for _ in range(n + 1)]

        def f(i, status):
            if status == final_status:
                return 0
            if i == n:
                return float('inf')
            if dp[i][status] != 0:
                return dp[i][status]
            p1 = f(i+1, status)
            p2 = 1 + f(i+1, status | people_skills[i])      # 用这个人了
            res = min(p1, p2)
            dp[i][status] = res
            return res

        min_people = f(0, 0)
        # print(*dp, sep='\n')
        res =[0] * min_people
        j = 0
        status = 0
        for i in range(n):
            if i + 1 == n or dp[i][status] != dp[i+1][status]:      # 用这个人了
                res[j] = i
                j += 1
                status |= people_skills[i]
                if j == min_people:
                    break
        return res

# req_skills = ["java","nodejs","reactjs"]
# people = [["java"],["nodejs"],["nodejs","reactjs"]]
req_skills = ["algorithms","math","java","reactjs","csharp","aws"]
people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
print(Solution().smallestSufficientTeam(req_skills, people))
